﻿namespace Leetcode.N0449.V2;

// 后序遍历
public class Codec
{
    public string serialize(TreeNode root)
    {
        IList<int> list = new List<int>();
        this.serialize(root, list);
        return string.Join(",", list);
    }

    private void serialize(TreeNode node, IList<int> list)
    {
        if (node == null)
        {
            return;
        }
        serialize(node.left, list);
        serialize(node.right, list);
        list.Add(node.val);
    }

    public TreeNode deserialize(string data)
    {
        if (string.IsNullOrEmpty(data))
        {
            return null;
        }
        var vals = data.Split(",").Select(i => int.Parse(i));
        var stack = new Stack<int>();
        foreach (var val in vals)
        {
            stack.Push(val);
        }
        return this.deserialize(stack, int.MinValue, int.MaxValue);
    }

    private TreeNode deserialize(Stack<int> stack, int min, int max)
    {
        if (stack.Count == 0 || stack.Peek() < min || stack.Peek() > max)
        {
            return null;
        }
        var val = stack.Pop();
        var node = new TreeNode(val);
        node.right = this.deserialize(stack, val, max);
        node.left = this.deserialize(stack, min, val);

        return node;
    }

}